package yz.com.javautil.astaralgorithm;

import yz.com.javautil.astar.AStarGrid;
import yz.com.javautil.astar.AStarNode;

import java.util.*;

/**
 * AStarAlgorithm算法实现
 *
 * @author csdn
 */
public class AStarGraphImpl<V> implements AStarGraph<V> {

    /**
     * 点列表
     */
    private List<V> vertexList;
    /**
     * 边矩阵（存储权值）
     */
    private int[][] edgeMatrix;
    /**
     * 边终点座标（用于计算H）
     */
    private String[][] edgeEndPoint;
    /**
     * 边数量
     */
    private int edgeNum;
    /**
     * 顶点数量
     */
    private int vertexNum;
    /**
     * 开启列表和关闭列表（A*优化列表）
     */
    private List<V> openList = new ArrayList<>(), closeList = new ArrayList<>();

    /**
     * 构造函数
     * 初始化顶点及边矩阵
     *
     * @param size 顶点数量
     */
    public AStarGraphImpl(int size) {
        // 初始化
        vertexList = new ArrayList<>();
        edgeMatrix = new int[size][size];
        edgeEndPoint = new String[size][size];
        this.edgeNum = 0;
        this.vertexNum = 0;

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == j) {
                    this.edgeMatrix[i][j] = 0;
                } else {
                    // 顶点i没有一条边直达顶点j
                    this.edgeMatrix[i][j] = Integer.MAX_VALUE;
                    this.edgeEndPoint[i][j] = "0.0 0.0";
                }
            }
        }
    }

    /**
     * 用于获取路径点位数据
     *
     * @param v0 开始点
     * @param vi 结束点
     * @return 返回路径
     */
    @Override
    public Vector<Integer> getPath(V v0, V vi) {
        // 待搜索的节点列表
        List<Integer> searchList = new ArrayList<>();
        // 距离
        int[] distanceArr = new int[this.vertexNum];
        // 路径
        int[] fromIndexArr = new int[this.vertexNum];
        // 获取开始及结束点索引值
        int startIndex = this.vertexList.indexOf(v0);
        int endIndex = this.vertexList.indexOf(vi);
        // 添加待搜索节点列表
        for (int i = 0; i < this.vertexNum; i++) {
            if (i == startIndex) {
                continue;
            }
            searchList.add(i);
        }
        // 获取距离并标记可达节点
        for (int i = 0; i < this.vertexNum; i++) {
            distanceArr[i] = this.edgeMatrix[startIndex][i];
            if (this.edgeMatrix[startIndex][i] == Integer.MAX_VALUE) {
                fromIndexArr[i] = -1;
            } else {
                fromIndexArr[i] = startIndex;
            }
        }
        int nearestIndexTemp;
        do {
            // 获取距离最小的节点
            nearestIndexTemp = searchList.get(0);
            for (int i = 1; i < searchList.size(); i++) {
                if (distanceArr[searchList.get(i)] < distanceArr[nearestIndexTemp]) {
                    nearestIndexTemp = searchList.get(i);
                }
            }
            // 从待搜索节点列表移除最小距离节点
            searchList.remove((Integer) nearestIndexTemp);
            // 继续搜索剩余节点
            for (int i = 0; i < this.vertexNum; i++) {
                int edgeDistance = this.edgeMatrix[nearestIndexTemp][i];
                // 判断是否是最短路径（两步的距离小于一步）并记录
                if (edgeDistance != 0 && edgeDistance < Integer.MAX_VALUE) {
                    if (edgeDistance + distanceArr[nearestIndexTemp] < distanceArr[i]) {
                        distanceArr[i] = edgeDistance + distanceArr[nearestIndexTemp];
                        fromIndexArr[i] = nearestIndexTemp;
                    }
                }
            }
        } while (nearestIndexTemp != endIndex && !searchList.isEmpty());
        // 从终点开始回溯到起点
        Stack<Integer> s = new Stack<>();
        int i = endIndex;
        // 压入终点
        s.push(endIndex);
        do {
            i = fromIndexArr[i];
            s.push(i);
        } while (i != startIndex);
        Vector<Integer> res = new Vector<>();
        while (!s.empty()) {
            res.add(s.pop());
        }
        return res;
    }

    /**
     * 通过A*算法获取路径点位数据
     *
     * @param v0 开始点
     * @param vi 结束点
     * @return 返回路径
     */
    public Vector<Integer> getPathByAStarAlgorithm(V v0, V vi) {
        // 待搜索的节点列表
        List<Integer> openList = new ArrayList<>();
        // 距离
        int[] distanceArr = new int[this.vertexNum];
        // 路径
        int[] fromIndexArr = new int[this.vertexNum];
        // 获取开始及结束点索引值
        int startIndex = this.vertexList.indexOf(v0);
        int endIndex = this.vertexList.indexOf(vi);
        // 获取距离并标记可达节点
        for (int i = 0; i < this.vertexNum; i++) {
            distanceArr[i] = this.edgeMatrix[startIndex][i];
            if (this.edgeMatrix[startIndex][i] == Integer.MAX_VALUE) {
                fromIndexArr[i] = -1;
            } else {
                fromIndexArr[i] = startIndex;
            }
        }

        // 添加待搜索节点列表
        inOpen(startIndex, openList);
        // 根据F值进行排序
        sortListByF(openList);
        int nearestIndexTemp;
        do {
            // 获取F值最小的节点
            nearestIndexTemp = openList.get(0);
            // 根据最小F值添加openList且从待搜索节点列表移除F值最小的节点
            inOpen(nearestIndexTemp, openList);
            openList.remove((Integer) nearestIndexTemp);
            sortListByF(openList);
            // 继续搜索剩余节点
            for (int i = 0; i < this.vertexNum; i++) {
                int edgeDistance = this.edgeMatrix[nearestIndexTemp][i];
                // 判断是否是最短路径（两步的距离小于一步）并记录
                if (edgeDistance != 0 && edgeDistance < Integer.MAX_VALUE) {
                    if (edgeDistance + distanceArr[nearestIndexTemp] < distanceArr[i]) {
                        distanceArr[i] = edgeDistance + distanceArr[nearestIndexTemp];
                        fromIndexArr[i] = nearestIndexTemp;
                    }
                }
            }
        } while (!openList.contains(endIndex));
        // 从终点开始回溯到起点
        Stack<Integer> s = new Stack<>();
        int i = endIndex;
        // 压入终点
        s.push(endIndex);
        do {
            i = fromIndexArr[i];
            s.push(i);
        } while (i != startIndex);
        Vector<Integer> res = new Vector<>();
        while (!s.empty()) {
            res.add(s.pop());
        }
        return res;
    }

    /**
     * 将点放入openList
     *
     * @param index    节点index
     * @param openList openList
     */
    private void inOpen(int index, List<Integer> openList) {
        Vector<Integer> adjacentEdge = getAdjacentEdge(index);
        openList.addAll(adjacentEdge);
    }

    /**
     * 根据F排序openList
     *
     * @param openList 待排序的数据
     */
    private void sortListByF(List<Integer> openList) {

    }


    /**
     * 将路径标记出来
     *
     * @param AStarNodeList 路径节点
     * @param AStarGrid     地图数据
     */
    public void showPath(List<AStarNode> AStarNodeList, AStarGrid AStarGrid) {
        // 从终点开始回溯到起点
        if (AStarNodeList.size() > 0) {
//            Node node = map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()];
            AStarNode AStarNode = AStarGrid.getEndAStarNode();
            while (!(AStarNode.getX() == AStarGrid.getStartAStarNode().getX() && AStarNode.getY() == AStarGrid.getStartAStarNode().getY())) {
                AStarNode.getFromAStarNode().setValue("*");
                AStarNode = AStarNode.getFromAStarNode();
            }
        }
        AStarGrid.getMap()[AStarGrid.getStartAStarNode().getX()][AStarGrid.getStartAStarNode().getY()].setValue("A");
    }

    @Override
    public void addEdge(V from, V to, String weightAndCoordinate) {
        int i = Integer.parseInt(from.toString());
        int j = Integer.parseInt(to.toString());
        this.edgeMatrix[i][j] = Integer.parseInt(weightAndCoordinate.split(",")[0]);
        this.edgeEndPoint[i][j] = weightAndCoordinate.split(",")[1];
        this.edgeNum++;

    }

    @Override
    public Vector<Integer> getAdjacentEdge(int v) {
        assert v >= 0 && v < vertexNum;
        Vector<Integer> adjacentEdgeVector = new Vector<>();
        for (int i = 0; i < vertexNum; i++) {
            if (edgeMatrix[v][i] != 0 && edgeMatrix[v][i] < Integer.MAX_VALUE) {
                adjacentEdgeVector.add(i);
            }
        }
        return adjacentEdgeVector;
    }

    @Override
    public int edgesSize() {
        return this.edgeNum;
    }

    @Override
    public int verticesSize() {
        return this.vertexNum;
    }

    @Override
    public void addVertex(V v) {
        this.vertexList.add(v);
        this.vertexNum++;
    }

    @Override
    public void removeEdge(V from, V to) {
        int i = Integer.parseInt(from.toString());
        int j = Integer.parseInt(to.toString());
        this.edgeMatrix[i][j] = Integer.MAX_VALUE;
        this.edgeNum--;
    }

    @Override
    public void removeVertex(V v) {
        int index = this.vertexList.indexOf(v);
        for (int i = 0; i < this.vertexNum; i++) {
            if (this.edgeMatrix[index][i] != 0) {
                this.edgeNum--;
            }
        }

        for (int i = index; i < this.vertexNum - 1; i++) {
            if (this.vertexNum >= 0) {
                System.arraycopy(this.edgeMatrix[i + 1], 0, this.edgeMatrix[i], 0, this.vertexNum);
            }
        }

        for (int i = 0; i < this.vertexNum; i++) {
            if (this.vertexNum - 1 - index >= 0) {
                System.arraycopy(this.edgeMatrix[i], index + 1, this.edgeMatrix[i], index, this.vertexNum - 1 - index);
            }
        }

        this.vertexList.remove(index);
        this.vertexNum--;
    }

    @Override
    public void displayGraph() {
        System.out.println("这是一个无向带权图（网、邻接矩阵）：");
        System.out.println("顶点：" + this.vertexList);
        System.out.println("网的邻接矩阵是：");
        for (int i = 0; i < this.vertexNum; i++) {
            for (int j = 0; j < this.vertexNum; j++) {
                if (this.edgeMatrix[i][j] == Integer.MAX_VALUE) {
                    System.out.print("∞\t");
                } else {
                    System.out.print(this.edgeMatrix[i][j] + "\t");
                }

            }
            System.out.println();
        }
    }

    @Override
    public int degree(V v) {
        // 获取顶点的序号
        int index = this.vertexList.indexOf(v);
        int count = 0;
        for (int i = 0; i < this.vertexNum; i++) {
            // 表示index与i之间有一条边
            if (this.edgeMatrix[index][i] != 0) {
                count++;
            }
        }
        return count;
    }

}
